package algorithm.dynamicProgramming.leetcode;

import java.util.Arrays;

//413. 等差数列划分
public class NumberOfArithmeticSlices {
    public static void main(String[] args) {
        int[] data = {1, 2, 3, 4};
        System.out.println(numberOfArithmeticSlicesP(data));
    }

    public static int numberOfArithmeticSlices(int[] nums) {

        int res = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            int cha = nums[i + 1] - nums[i];
            for (int j = i + 1; j < nums.length - 1; j++) {
                if (nums[j + 1] - nums[j] == cha) {
                    res++;
                } else {
                    break;
                }
            }
        }

        return res;
    }


    //dp
    public static int numberOfArithmeticSlices3(int[] nums) {
        int len = nums.length;
        if (len < 3) {
            return 0;
        }
        int[] f = new int[len];
        int res = 0;
        for (int i = 2; i < len; i++) {
            if (nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]) {
                f[i] = f[i - 1] + 1;
                res += f[i];
            }
        }
        System.out.println(Arrays.toString(f));
        return res;
    }


    // 二战 暴力
    public static int numberOfArithmeticSlicesP(int[] nums) {
        if (nums.length <= 2) {
            return 0;
        }
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j <= nums.length; j++) {
                if (j - i + 1 > 3) {
                    int[] f = new int[j - i];
                    System.arraycopy(nums, i, f, 0, j - i);
                    if (isOK(f, 0, j - i)) {
                        count++;
                    }

                }
            }
        }
        return count;
    }

    // 判断是否是等差数列
    private static boolean isOK(int[] nums, int i, int j) {
        int p = i;
        int q = i + 1;
        int d = nums[q] - nums[p];
        for (int k = p + 1; k < j; k++) {
            if (nums[k] != d * (k) + nums[i]) {
                return false;
            }
        }
        return true;
    }

    // 暴力
    public static int numberOfArithmeticSlicesP2(int[] nums) {
        if (nums.length <= 2) {
            return 0;
        }
        int count = 0;
        int add = 0;
        for (int i = 2; i < nums.length; i++) {
            if (nums[i - 2] - nums[i - 1] == nums[i - 1] - nums[i]) {
                add++;
                count += add;

            } else {
                add = 0;
            }
        }
        return count;
    }
}
